package tree.binary_tree.heap.app;

/**
 * 堆的应用：
 * 堆排序
 * 求top n、
 * 优先级队列 todo
 * 求中位数
 * <p>
 * 对于完全二叉树来说，下标从 n/2​+1 到 n 的节点都是叶子节点。
 * 堆排序：1.堆化，2.排序
 *
 * @author yeyangtao created at 16:53 2020/10/14
 */
public class HeapSort {
    /**
     * 建堆
     */
    private static void buildHeap(int[] a, int n) {
        for (int i = n / 2; i >= 1; i--) {
            //自上向下堆化
            heaping(a, n, i);
        }
    }

    private static void heaping(int[] a, int n, int i) {
        while (true) {
            int maxPos = i;
            if (i * 2 <= n && a[i] < a[i * 2]) maxPos = i * 2;
            if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) maxPos = i * 2 + 1;
            if (maxPos == i) break;
            //交换
            int temp = a[i];
            a[i] = a[maxPos];
            a[maxPos] = temp;

            i = maxPos;
        }
    }

    /**
     * 堆排序，把堆顶与最后一个交换然后堆化，然后再与倒数第二个交换堆化
     */
    public static void sort(int[] a, int n) {
        buildHeap(a, n);
        int k = n;
        while (k > 1) {
            int temp = a[1];
            a[1] = a[k];
            a[k] = temp;

            k--;
            heaping(a, k, 1);
        }
    }
}
